package com.sunny.l11;

import java.util.*;

public class Solution {

    Map<Integer, ArrayList<Integer>> map = new HashMap<>();

    ArrayList<String> res = new ArrayList<>();

    Map<Integer, ArrayList<String>> smap = new HashMap<>();

//    public static void main(String[] args) {
//
//        String s = "catsanddog";
//        Set<String> dict = new HashSet<>(Arrays.asList("cat", "cats", "and", "sand", "dog","d","og","an"));
//
//        Solution solution = new Solution();
//
//        List<String> r = solution.wordBreak(s, dict);
//
//        r.forEach(System.out::println);
//
//    }

    public List<String> wordBreak(String s, List<String> dict) {

        pre(s, dict);

//        dfs(s ,0, s.length(), new StringBuilder());
//
//        return res;
        return dfs(s, 0);

    }

    public ArrayList<String> dfs(String s, int ind){
//        System.out.println(s + " " + ind);
        if(smap.containsKey(ind)){
            return smap.get(ind);
        }
        int len = s.length();
        ArrayList<String> list = new ArrayList<>();
        if(ind == len){
            list.add("");
        }else if(map.containsKey(ind)){
            for(Integer jInd: map.get(ind)){
//                System.out.println("*******"+jInd);
                String tmpStr = s.substring(ind,jInd+1);
                ArrayList<String> tmpList = dfs(s, jInd+1);
                if(0 == tmpList.size()){
                    continue;
                }
                StringBuilder sb;
                for(String t: tmpList){
                    if("".equals(t)){
                        sb = new StringBuilder(tmpStr);
                    }else
                        sb = new StringBuilder(tmpStr).append(" ").append(t);
//                    System.out.println("&&&&&&&&&&"+sb);
                    list.add(sb.toString());
                }
            }
        }
        smap.put(ind,list);
        return list;
    }

    public void dfs( String s, int ind, int len, StringBuilder result){
        if(map.containsKey(ind)){
            for(Integer jInd: map.get(ind)){
                if(jInd == len-1){

                    String tmpStr = s.substring(ind,jInd+1);
                    if ("".equals(result.toString())) {
                        result.append(tmpStr);
                    } else {
                        result.append(" ").append(tmpStr);
                    }
//                    r.add(result.toString());
                    res.add(result.toString());
                    int delLen = tmpStr.length();
                    if(result.toString().contains(" ")){
                        delLen++;
                    }
                    result.delete(result.length()-delLen,result.length());
                }else {
                    int newI = jInd + 1;
                    if (map.containsKey(newI)) {
                        String tmpStr = s.substring(ind,jInd+1);
                        if ("".equals(result.toString())) {
                            result.append(tmpStr);
                        } else {
                            result.append(" ").append(tmpStr);
                        }
                        dfs(s, newI, len, result);
                        int delLen = tmpStr.length();
                        if(result.toString().contains(" ")){
                            delLen++;
                        }
                        result.delete(result.length()-delLen,result.length());
                    }
                }
            }
        }
    }

    public void pre(String s, List<String> dict){
        for(int i=0;i<s.length();i++){
            ArrayList<Integer> tmpList = new ArrayList<>();
            for(int j=i;j<s.length();j++){
                String tmpStr = s.substring(i, j + 1);
//                    System.out.println(i+" " + j + " " + tmpStr + " " + dict.contains(tmpStr));
                if (dict.contains(tmpStr)){
                    tmpList.add(j);
                }
            }
            Collections.reverse(tmpList);
            map.put(i, tmpList);
        }
    }

}